package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月22日
*时间：下午4:43:24
*/
public class Q18 {
    /**
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    ArrayList<ArrayList<Integer>> rs = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null || nums.length <= 0) {
            rs.add(new ArrayList<Integer>());
            return rs;
        }
        Arrays.asList(nums);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            Integer count = map.get(i);
            if (count == null) {
                map.put(i, 1);
            } else {
                map.put(i, count + 1);
            }
        }
        List<Integer> single = new ArrayList<>();
        List<Map.Entry<Integer, Integer>> multiple = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            if (e.getValue() == 1) {
                single.add(e.getKey());
            } else {
                multiple.add(e);
            }
        }
        int length = single.size();
        long n = (long) Math.pow(2, length);
        for (long i = 0; i < n; i++) {
            long k = i;
            ArrayList<Integer> result = new ArrayList<>();
            for (int j = 0; j < length; j++) {
                if ((k & 1) == 1) {
                    result.add(single.get(j));
                }
                k = (k >> 1);
            }
            build(result, multiple, multiple.size(), 0);
        }
        return rs;
    }

    private void build(ArrayList<Integer> result, List<Map.Entry<Integer, Integer>> multiple, int size, int i) {
        ArrayList<Integer> l = new ArrayList<>(result);
        if (i >= size) {
            Collections.sort(l);
            rs.add(l);
        } else {
            Map.Entry<Integer, Integer> e = multiple.get(i);
            for (int p = 0; p <= e.getValue(); p++) {
                add(p, e.getKey(), l);
                build(l, multiple, size, i + 1);
                l = new ArrayList<>(result);
            }
        }
    }

    private void add(int p, Integer value, ArrayList<Integer> l) {
        for (int i = 0; i < p; i++) {
            l.add(value);
        }
    }

    @Test
    public void testA() {
        int[] nums = { 1, 2, 3 };
        System.out.println(subsetsWithDup(nums));
    }

}
